{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Feature importance method in sci-kit learn (Solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll get a sense of how feature importance is calculated in sci-kit learn, and also see where it gives results that we wouldn't expect.\n",
    "\n",
    "Sci-kit learn uses gini impurity to calculate a measure of impurity for each node.  Gini impurity, like entropy is a way to measure how \"organized\" the observations are before and after splitting them using a feature. So there is an impurity measure for each node.\n",
    "\n",
    "In the formula, freq_{i} is the frequency of label \"i\".  C is the number of unique labels at that node.\n",
    "\n",
    "$Impurity= \\sum_{i=1}^{C} - freq_{i} * (1- freq_{i})$\n",
    "\n",
    "The node importance in sci-kit learn is calculated as the difference between the gini impurity of the node and the gini impurity of its left and right children.  These gini impurities are weighted by the number of data points that reach each node.\n",
    "\n",
    "$NodeImportance = w_{i} Impurity_{i} - ( w_{left} Impurity_{left} + w_{right} Impurity_{right} )$\n",
    "\n",
    "The importance of a feature is the importance of the node that it was split on, divided by the sum of all node importances in the tree.  You’ll get to practice this in the coding exercise coming up next!\n",
    "\n",
    "For additional reading, please check out this blog post [The Mathematics of Decision Trees, Random Forest and Feature Importance in Scikit-learn and Spark](https://medium.com/@srnghn/the-mathematics-of-decision-trees-random-forest-and-feature-importance-in-scikit-learn-and-spark-f2861df67e3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "!{sys.executable} -m pip install numpy==1.14.5\n",
    "!{sys.executable} -m pip install scikit-learn==0.19.1\n",
    "!{sys.executable} -m pip install graphviz==0.9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sklearn\n",
    "from sklearn import tree\n",
    "import numpy as np\n",
    "import graphviz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generate data\n",
    "\n",
    "We'll generate features and labels that form the \"AND\" operator.  So when feature 0 and feature 1 are both 1, then the label is 1, else the label is 0.  The third feature, feature 2, won't have an effect on the label output (it's always zero)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Features 0 and 1 form the AND operator\n",
    "Feature 2 is always zero.\n",
    "\"\"\"\n",
    "N = 100\n",
    "M = 3\n",
    "X = np.zeros((N,M))\n",
    "X.shape\n",
    "y = np.zeros(N)\n",
    "X[:1 * N//4, 1] = 1\n",
    "X[:N//2, 0] = 1\n",
    "X[N//2:3 * N//4, 1] = 1\n",
    "y[:1 * N//4] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# observe the features\n",
    "X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# observe the labels\n",
    "y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Train a decision tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "model = tree.DecisionTreeClassifier(random_state=0)\n",
    "model.fit(X, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualize the trained decision tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dot_data = sklearn.tree.export_graphviz(model, out_file=None, filled=True, rounded=True, special_characters=True)  \n",
    "graph = graphviz.Source(dot_data)  \n",
    "graph "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Explore the tree\n",
    "\n",
    "The [source code for Tree](https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/tree/_tree.pyx) has useful comments about attributes in the Tree class.  Search for the code that says `cdef class Tree:` for useful comments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get the Tree object\n",
    "tree0 = model.tree_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tree attributes are stored in lists\n",
    "\n",
    "The tree data are stored in lists.  Each node is also assigned an integer 0,1,2...  \n",
    "Each node's value for some attribute is stored at the index location that equals the node's assigned integer.\n",
    "\n",
    "For example, node 0 is the root node at the top of the tree.  There is a list called children_left.  Index location 0 contains the left child of node 0.\n",
    "\n",
    "\n",
    "#### left and right child nodes\n",
    "```\n",
    "children_left : array of int, shape [node_count]\n",
    "        children_left[i] holds the node id of the left child of node i.\n",
    "        For leaves, children_left[i] == TREE_LEAF. Otherwise,\n",
    "        children_left[i] > i. This child handles the case where\n",
    "        X[:, feature[i]] <= threshold[i].\n",
    "children_right : array of int, shape [node_count]\n",
    "        children_right[i] holds the node id of the right child of node i.\n",
    "        For leaves, children_right[i] == TREE_LEAF. Otherwise,\n",
    "        children_right[i] > i. This child handles the case where\n",
    "        X[:, feature[i]] > threshold[i].\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"tree0.children_left: {tree0.children_left}\")\n",
    "print(f\"tree0.children_right: {tree0.children_right}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So in this tree, the index positions 0,1,2,3,4 are the numbers for identifying each node in the tree.  Node 0 is the root node.  Node 1 and 2 are the left and right child of the root node.  So in the list children_left, at index 0, we see 1, and for children_right list, at index 0, we see 2.  \n",
    "\n",
    "-1 is used to denote that there is no child for that node.  Node 1 has no left or right child, so in the children_left list, at index 1, we see -1.  Similarly, in children_right, at index 1, the value is also -1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### features used for splitting at each node\n",
    "```\n",
    "    feature : array of int, shape [node_count]\n",
    "        feature[i] holds the feature to split on, for the internal node i.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"tree0.feature: {tree0.feature}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The feature 1 is used to split on node 0.  Feature 0 is used to split on node 2.  The -2 values indicate that these are leaf nodes (no features are used for splitting at those nodes)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### number of samples in each node\n",
    "\n",
    "```\n",
    "n_node_samples : array of int, shape [node_count]\n",
    "        n_node_samples[i] holds the number of training samples reaching node i.\n",
    "\n",
    "weighted_n_node_samples : array of int, shape [node_count]\n",
    "        weighted_n_node_samples[i] holds the weighted number of training samples\n",
    "        reaching node i.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"tree0.n_node_samples : {tree0.n_node_samples}\")\n",
    "print(f\"tree0.weighted_n_node_samples : {tree0.weighted_n_node_samples}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The weighted_n_node_samples is the same as n_node_samples for decision trees.  It's different for random forests where a sub-sample of data points is used in each tree.  We'll use weighted_n_node_samples in the code below, but either one works when we're calculating the proportion of samples in a left or right child node relative to their parent node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gini impurity\n",
    "\n",
    "Gini impurity, like entropy is a way to measure how \"organized\" the observations are before and after splitting them using a feature. So there is an impurity value calculated for each node.\n",
    "\n",
    "In the formula, $freq_{i}$ is the frequency of label \"i\".  C is the number of unique labels at that node (C stands for \"Class\", as in \"classifier\".\n",
    "\n",
    "$ \\sum_{i}^{C} - freq_{i} * (1- freq_{i})$\n",
    "\n",
    "```\n",
    "impurity : array of double, shape [node_count]\n",
    "        impurity[i] holds the impurity (i.e., the value of the splitting\n",
    "        criterion) at node i.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is the impurity if there is a single class (unique label type)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "freq0 = 1\n",
    "impurity = -1 * freq0 * (1 - freq0)\n",
    "print(f\"impurity of a homogenous sample with a single label, is: {impurity}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is the impurity if there are two classes (two distinct labels), and there are 90% of samples for one label, and 10% for the other?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "freq1 = 0.9\n",
    "freq2 = 0.1\n",
    "impurity = -1 * freq1 * (1 -freq1) + -1 * freq2 * (1 - freq2)\n",
    "print(f\"impurity when 90% are of one label, and 10% are of the other: {impurity}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quiz\n",
    "What is the impurity if there are two classes of label, and there are 50% of samples for one label, and 50% for the other?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "What is the impurity if there are two classes of label,\n",
    "and there are 50% of samples for one label, and 50% for the other?\n",
    "\"\"\"\n",
    "# TODO\n",
    "freq1 = 0.5\n",
    "freq2 = 0.5\n",
    "# TODO\n",
    "impurity = -1 * freq1 * (1 - freq1) + -1 * freq2 * (1 - freq2)\n",
    "print(f\"impurity when 50% are of one label, and 50% are of the other: {impurity}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quiz\n",
    "\n",
    "Is the impurity larger or smaller (in magnitude) when the samples are dominated by a single class?  \n",
    "Is the impurity larger or smaller (in magnitude) when the frequency of each class is more evenly distributed among classes?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Answer\n",
    "The gini impurity is smaller in magnitude (closer to zero) when the samples are dominated by a single class.  \n",
    "The impurity is larger in magnitude (farther from zero) when there is a more even split among labels in the sample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Node Importance\n",
    "\n",
    "The node importance in sklearn is calculated as the difference between the gini impurity of the node and the impurities of its child nodes.  These gini impurities are weighted by the number of data points that reach each node.\n",
    "\n",
    "$NodeImportance = w_{i} Impurity_{i} - ( w_{left} Impurity_{left} + w_{right} Impurity_{right} )$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Summary of the node labels\n",
    "Node 0 is the root node, and its left and right children are 1 and 2.  \n",
    "Node 1 is a leaf node  \n",
    "Node 2 has two children, 3 and 4.  \n",
    "Node 3 is a leaf node  \n",
    "Node 4 is a leaf node  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# summary of child nodes\n",
    "print(f\"tree0.children_left: {tree0.children_left}\")\n",
    "print(f\"tree0.children_right: {tree0.children_right}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculate the node importance of the root node, node 0.  Its child nodes are 1 and 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ni0 = tree0.weighted_n_node_samples[0] * tree0.impurity[0] - \\\n",
    "        ( tree0.weighted_n_node_samples[1] * tree0.impurity[1] + \\\n",
    "          tree0.weighted_n_node_samples[2] * tree0.impurity[2] )\n",
    "print(f\"Importance of node 0 is {ni0}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quiz\n",
    "Calculate the node importance of node 2.  Its left and right child nodes are 3 and 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO\n",
    "ni2 = tree0.weighted_n_node_samples[2] * tree0.impurity[2] - \\\n",
    "        ( tree0.weighted_n_node_samples[3] * tree0.impurity[3] + \\\n",
    "          tree0.weighted_n_node_samples[4] * tree0.impurity[4] )\n",
    "print(f\"Importance of node 2 is {ni2}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The other nodes are leaf nodes, so there is no decrease in impurity that we can calculate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Sum the node importances\n",
    "Only nodes 0 and node 2 have node importances.  The others are leaf nodes, so we don't calculate node importances (there is no feature that is used for splitting at those leaf nodes)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO\n",
    "ni_total = ni0 + ni2\n",
    "print(f\"The sum of node importances is {ni_total}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Summary of which feature is used to split at each node\n",
    "\n",
    "feature 0 was used to split on node 2  \n",
    "feature 1 was used to split on node 0  \n",
    "feature 2 was not used for splitting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"tree0.feature: {tree0.feature}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quiz: Calculate importance of the features\n",
    "\n",
    "The importance of a feature is the importance of the node that it was used for splitting, divided by the total node importances.  Calculate the importance of feature 0, 1 and 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO\n",
    "fi0 = ni2/ni_total\n",
    "fi1 = ni0/ni_total\n",
    "fi2 = 0/ni_total\n",
    "print(f\"importance of feature 0: {fi0}\")\n",
    "print(f\"importance of feature 1: {fi1}\")\n",
    "print(f\"importance of feature 2: {fi2}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Double check with sklearn\n",
    "\n",
    "Check out how to use [feature importance](https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier.feature_importances_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO: get feature importances from sci-kit learn\n",
    "\n",
    "fi0_skl = model.feature_importances_[0]\n",
    "fi1_skl = model.feature_importances_[1]\n",
    "fi2_skl = model.feature_importances_[2]\n",
    "\n",
    "print(f\"sklearn importance of feature 0: {fi0_skl}\")\n",
    "print(f\"sklearn importance of feature 1: {fi1_skl}\")\n",
    "print(f\"sklearn importance of feature 2: {fi2_skl}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notice anything odd?\n",
    "\n",
    "Notice that the data we generated simulates an AND operator.  If feature 0 and feature 1 are both 1, then the output is 1, otherwise 0.  So, from that perspective, do you think that features 0 and 1 are equally important?\n",
    "\n",
    "What do you notice about the feature importance calculated in sklearn?  Are the features considered equally important according to this calculation?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Answer\n",
    "Intuitively, if features 0 and 1 form the AND operator, then it makes sense that they should be equally important in determining the output.  The feature importance calculated in sklearn assigns a higher importance to feature 0 compared to feature 1.  This is because the tree first splits on feature 1, and then when it splits on feature 0, the labels become cleanly split into respective leaf nodes.  \n",
    "\n",
    "In other words, what we observe is that features which are used to split further down the bottom of the tree are given higher importance, using the gini impurity as a measure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "If someone tells you that you don't need to understand the algorithm, just how to install the package and call the function, do you agree or disagree with that statement?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution notebook\n",
    "[Solution notebook](sklearn_feature_importance_solution.ipynb)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_p7a",
   "language": "python",
   "name": "env_p7a"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
